The Archeologists' Dilemma
Category:Problemas =Problema= The Archeologists' Dilemma no site da UVA = Resumo= Dado 1 \leq N \leq 2^{31} inteiro com D dígitos, encontre o menor E tal que: * 2^E tem pelo menos 2D+1 dígitos; * os D primeiros dígitos da representação decimal de 2^E são iguais a N . Por exemplo, para N = 10 a resposta é E = 20 , já que 2^E = \textbf{10}48576 . Note que E = 10 não é uma solução válida, já que 2^E = \textbf{10}24 tem apenas 4 dígitos, quando o mínimo necessário é 5. =Solução= Em primeiro lugar, nós reduzimos a dimensão dos números do problema trabalhando com logaritmos: \begin{matrix} N \times 10^k \leq & 2^E & < (N+1) \times 10^k \quad \Leftrightarrow \\ \Leftrightarrow \quad k + \log_{10} N \leq & E \log_{10} 2 & < k + \log_{10} (N+1) \end{matrix} Como N é inteiro, tomar os três lados da desigualdade módulo 1 preserva as desigualdades; definindo \{x\} = x - \left\lfloor x \right\rfloor , a desigualdade acima é quievalente a \{\log_{10} N\} \leq \{E \log_{10} 2\} < \{\log_{10} (N+1)\} O primeiro cuidado que devemos ter é com a precisão dos números envolvidos: para N = 2^{31} , a largura do intervalo acima é 2.02 \times 10^{-10} \approx 2^{-32.2} ; escolhendo um valor de E aleatório, essa é a probabilidade de que ele seja a solução do problema, pelo Teorema de Kronecker. Logo, devemos esperar que para valores de N nesta faixa, a resposta seja da ordem de \left( 2.02 \times 10^{-10} \right)^{-1} \approx 4.94 \times 10^9 \approx 2^{32.2} , com um desvio padrão muito parecido (supondo uma distribuição geométrica para as respostas do problema). Mesmo com precisão de long double (i.e. 64 bits), o erro de representação de \log_{10} 2 é 2^{-65} ; quando multiplicado por E , esse erro aumenta para 2^{-32.8} , que é apenas 2^{-0.6} \approx 0.75 vezes a largura do intervalo no pior caso. Portanto, é crucial fazermos todos os esforços possíveis para manter bits de precisão durante a conta. Um fato que ajuda é que temos um tipo de inteiro com 64 bits de precisão: uint64_t. Podemos, por exemplo, implementar a seguinte função para calcular a parte fracionária de \log_{10} x : uint64_t log_10(uint64_t N) { long double n = N, p = 1.0; while ((10.0 * p) >= n) p *= 10.0; return (uint64_t)(log10l(n / p) * 0x1.0p+64); } Note que nós não fizemos while (n >= 10.0) n /= 10.0; para evitar erros de precisão: as únicas duas operações inexatas na função acima são a divisão e o log10l da última linha. Fazer a conta com uint64_t ao invés de diretamente com long doubles tem uma vantagem fundamental: o overflow de uint64_t é equivalente a tirar a parte fracionária, sem perder precisão, como ocorreria se fizéssemos a conta com long doubles; a parte inteira dos logaritmos ocuparia um ou dois bits, que seriam perdidos na mantissa do número resultante. Munido de log_10, poderíamos simplesmente testar todos os valores possíveis de E , em ordem, até encontrar um que estivesse no intervalo desejado: isso leva tempo \Theta(E) , que como mencionado acima, pode ser muito grande. Uma alternativa é o algoritmo baby-step giant-step : escolha um m qualquer -- a escolha ótima do valor de m será discutida logo em breve. Pelo algoritmo de divisão euclideana, E = mq + r , onde 0 \leq r < m . Calcule todos os produtos r \log_{10} 2 com r nesse intervalo, e guarde os valores obtidos em alguma estrutura de dados que permita buscar o primeiro elemento \geq x em \Theta\left(\log m\right) (e.g. um vetor ordenado). Depois, testamos todos os valores de q em ordem: é fácil ver que \begin{matrix} \{\log_{10} N\} \leq & \{(mq + r) \log_{10} 2\} & < \{\log_{10} (N+1)\} \quad \Leftrightarrow \\ \Leftrightarrow \quad \{\log_{10} N - q (m \log_{10} 2)\} \leq & \{r \log_{10} 2\} & < \{\log_{10} (N+1) - q (m \log_{10} 2)\} \end{matrix} e que, portanto, fixado um valor de q , basta verificar se algum dos m valores de \{r \log_{10} 2\} está dentro do intervalo \left[\{\log_{10} N - q (m \log_{10} 2)\}, \{\log_{10} (N+1) - q (m \log_{10} 2)\}\right[ (tomando cuidado com a possibilidade de que \{\log_{10} (N+1) - q (m \log_{10} 2)\} < \{\log_{10} N - q (m \log_{10} 2)\} , apesar de que neste caso podemos simplesmente tomar r = 0 ). Cada verificação custa \Theta\left(\log m\right) . Qual é a complexidade deste algoritmo? Pré-calcular e ordenar os \{r \log_{10} 2\} custa \Theta\left(m \log m\right) ; testar todos os valores de q até encontrar o valor certo custa \Theta\left(\frac{E}{m} \log m\right) , para um custo total de \Theta\left(\left(m + \frac{E}{m}\right) \log m\right) . O valor mínimo da complexidade é atingido quando m \sim \sqrt{E} , para um custo de \tilde{\Theta}\left(\sqrt{E}\right) . Calcular m \log_{10} 2 é mais complicado do que parece: se escolhermos, e.g. m = 2^{18} , e fizermos a conta primeiro calculando o logaritmo e depois multiplicando por m perdemos 18 bits de precisão. A abordagem correta é elevar 2 ao quadrado 18 vezes, dividindo por uma potência de 10 apropriada sempre que o valor se tornar muito grande: uint64_t log_10_2_2(size_t E) { long double x = 2.0; size_t i; for (i = 0; i < E; i++) { x *= x; if (x >= exp10l(8)) x /= exp10l(8); } if (x >= exp10l(4)) x /= exp10l(4); if (x >= exp10l(2)) x /= exp10l(2); if (x >= exp10l(1)) x /= exp10l(1); return (uint64_t)(log10l(x) * 0x1.0p+64); } Finalmente, falta a restrição do número de dígitos, mas essa é a mais simples de todas: um inteiro k tem \left\lfloor \log_{10} k \right\rfloor + 1 dígitos; logo devemos ter \begin{matrix} \left\lfloor \log_{10} 2^E \right\rfloor + 1 & \geq & 2\left\lfloor \log_{10} N \right\rfloor + 3 \quad \Leftrightarrow \\ \Leftrightarrow \quad \left\lfloor E \log_{10} 2 \right\rfloor & \geq & 2\left\lfloor \log_{10} N \right\rfloor + 2 \end{matrix} Como o lado direito da última desigualdade é inteiro, o piso do lado esquerdo é redundante, e portanto é necessário e suficiente que E \geq \frac{2\left(\left\lfloor \log_{10} N \right\rfloor + 1\right)}{\log_{10} 2} =Exemplo= Entrada 1 2 3 4 5 6 7 8 9 9 99 999 9999 99999 999999 9999999 99999999 999999999 1 10 100 1000 10000 100000 1000000 10000000 100000000 1000000000 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 1048576 2097152 4194304 8388608 16777216 33554432 67108864 134217728 268435456 536870912 1073741824 2147483648 Saída 7 8 15 12 9 16 46 13 53 53 93 2621 13301 254370 5781869 38267831 146964308 1923400330 7 20 196 2136 15437 70777 325147 6432163 198096465 15042141867 7 8 12 13 14 15 109 203 689 1660 2146 2147 2148 15450 28752 70792 70793 70794 325165 325166 325167 325168 6432185 6432186 6432187 51132182 51132183 198096492 888218039 1578339586 18888942557 51586748168